package everydayone.reversePair;
/**
 * @Date 2020/04/24
 * @author 王光浩
 * @Thinking 使用并归排序方法。
 * 		在并归的过程中，我们统计右边部分小于左边部分的数目，然后将结果返回。
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（1）
 */
public class MyMethodThree {
	public int reversePairs(int[] nums) {
		if( nums==null || nums.length<2 ) return 0;
		return helper(0,nums.length-1,nums);
	}
	private int helper( int l , int r , int[] nums) {
		if( l>=r ) return 0;
		int mid = (l+r)/2;
		int left = l;
		int right = mid+1;
		//进行递归
		int sum = 0;
		sum += helper(l,mid,nums);
		sum += helper(right,r,nums);
		
		int[] temp = new int[r-l+1];
		int index = 0;
		//统计两个数组中 逆序对的数目
		int pre = 0;
		while( left<=mid && right<=r) {
			 if( nums[left]>nums[right] ) {
				 temp[index++] = nums[right++];
				 pre++;
			 } else {
				 temp[index++] = nums[left++];
				 sum += pre;
			 }
		}
		
		if( left>mid ) {
			while( right<=r ) temp[index++] = nums[right++];
		}
		if( right>r ) {
			while( left<=mid )	{
				temp[index++] = nums[left++];
				sum += pre;
			}
		}
		index = 0;
		for( int i=l ; i<=r ; i++ ) 
			nums[i] = temp[index++];
		return sum;
	}
}
